#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 15;

int n, m;
int a[N];
vector<int> b[N];
int ans;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
bool check(int i, int x) {
  for (int y : b[i])
    if (gcd(x, y) != 1) return false;
  return true;
}
void dfs(int s, int cnt) {
  if (s == n + 1) {
    ans = min(ans, cnt);
    return;
  }
  rep(i, 1, cnt) {
    if (check(i, a[s])) {
      b[i].push_back(a[s]);
      dfs(s + 1, cnt);
      b[i].pop_back();
    }
  }
  b[cnt + 1].push_back(a[s]);
  dfs(s + 1, cnt + 1);
  b[cnt + 1].pop_back();
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  rep(i, 1, n) cin >> a[i];
  ans = n;
  dfs(1, 0);
  cout << ans;
  return 0;
}